package doublePointer;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class FourSum {

    private List<List<Integer>> ans = new LinkedList<>();

    /**
     * LeetCode T18 四数之和
     * @param args
     */
    public static void main(String[] args) {

    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        if (nums == null || nums.length == 0){
            return ans;
        }
        //进行排序操作
        Arrays.sort(nums);
        int len = nums.length;
        List<Integer> trace = new LinkedList<>();
        backtrace(nums, 0, target, trace);
        return ans;
    }

    public void backtrace(int[] nums, int beginIndex, int target, List<Integer> trace){
        if (trace.size() == 4){
            if (target == 0){
                ans.add(new LinkedList<>(trace));
            }
            return;
        }
        if (target < 0){
            return;
        }
        for (int i = beginIndex; i < nums.length; i++){
            //重置选择列表，重置时不能让其他元素影响到本层
            if (i > beginIndex && nums[i] == nums[i - 1]){
                continue;
            }
            trace.add(nums[i]);
            backtrace(nums, i + 1, target - nums[i], trace);
            trace.remove(trace.size() - 1);
        }
    }
}
